home *** CD-ROM | disk | FTP | other *** search
/ Aminet 31 / Aminet 31 (1999)(Schatztruhe)[!][Jun 1999].iso / Aminet / dev / c / ctags.lha / ctags-3.0.3 / keyword.c < prev    next >
C/C++ Source or Header  |  1999-02-17  |  7KB  |  263 lines
  1. /*****************************************************************************
  2. *   $Id: keyword.c,v 7.3 1998/12/16 03:56:10 darren Exp $
  3. *
  4. *   Copyright (c) 1998, Darren Hiebert
  5. *
  6. *   This source code is released for free distribution under the terms of the
  7. *   GNU General Public License.
  8. *
  9. *   Manages a keyword hash.
  10. *****************************************************************************/
  11.  
  12. /*============================================================================
  13. =   Include files
  14. ============================================================================*/
  15. #include "general.h"
  16.  
  17. #include <string.h>
  18.  
  19. #include "debug.h"
  20. #include "keyword.h"
  21. #include "main.h"
  22. #include "options.h"
  23.  
  24. /*============================================================================
  25. =   Macros
  26. ============================================================================*/
  27. #define HASH_EXPONENT    7    /* must be less than 17 */
  28.  
  29. /*============================================================================
  30. =   Data declarations
  31. ============================================================================*/
  32. typedef struct sHashEntry {
  33.     const char *string;
  34.     struct sHashEntry *next;
  35.     int value[LANG_COUNT];
  36. } hashEntry;
  37.  
  38. /*============================================================================
  39. =   Data definitions
  40. ============================================================================*/
  41. const unsigned int TableSize = 1 << HASH_EXPONENT;
  42. static hashEntry **HashTable = NULL;
  43.  
  44. /*============================================================================
  45. =   Function prototypes
  46. ============================================================================*/
  47. static hashEntry **getHashTable __ARGS((void));
  48. static hashEntry *getHashTableEntry __ARGS((unsigned int hashedValue));
  49. static unsigned int hashValue __ARGS((const char *const string));
  50. static hashEntry *newEntry __ARGS((const char *const string, langType language, int value));
  51.  
  52. /*============================================================================
  53. =   Function definitions
  54. ============================================================================*/
  55.  
  56. static hashEntry **getHashTable()
  57. {
  58.     static boolean allocated = FALSE;
  59.  
  60.     if (! allocated)
  61.     {
  62.     unsigned int i;
  63.  
  64.     HashTable =(hashEntry**)eMalloc((size_t)TableSize * sizeof(hashEntry*));
  65.  
  66.     for (i = 0  ;  i < TableSize  ;  ++i)
  67.         HashTable[i] = NULL;
  68.  
  69.     allocated = TRUE;
  70.     }
  71.     return HashTable;
  72. }
  73.  
  74. static hashEntry *getHashTableEntry( hashedValue )
  75.     unsigned int hashedValue;
  76. {
  77.     hashEntry **const table = getHashTable();
  78.     hashEntry *entry;
  79.  
  80.     Assert(hashedValue < TableSize);
  81.     entry = table[hashedValue];
  82.  
  83.     return entry;
  84. }
  85.  
  86. static unsigned int hashValue( string )
  87.     const char *const string;
  88. {
  89.     unsigned long value = 0;
  90.     const unsigned char *p;
  91.  
  92.     Assert(string != NULL);
  93.  
  94.     /*  We combine the various words of the multiword key using the method
  95.      *  described on page 512 of Vol. 3 of "The Art of Computer Programming".
  96.      */
  97.     for (p = (const unsigned char *)string  ;  *p != '\0'  ;  ++p)
  98.     {
  99.     value <<= 1;
  100.     if (value & 0x00000100L)
  101.         value = (value & 0x000000ffL) + 1L;
  102.     value ^= *p;
  103.     }
  104.     /*  Algorithm from page 509 of Vol. 3 of "The Art of Computer Programming"
  105.      *  Treats "value" as a 16-bit integer plus 16-bit fraction.
  106.      */
  107.     value *= 40503L;        /* = 2^16 * 0.6180339887 ("golden ratio") */
  108.     value &= 0x0000ffffL;    /* keep fractional part */
  109.     value >>= 16 - HASH_EXPONENT; /* scale up by hash size and move down */
  110.  
  111.     return value;
  112. }
  113.  
  114. static hashEntry *newEntry( string, language, value )
  115.     const char *const string;
  116.     langType language;
  117.     int value;
  118. {
  119.     hashEntry *const entry = (hashEntry *)eMalloc(sizeof(hashEntry));
  120.     unsigned int i;
  121.  
  122.     entry->string = string;
  123.     entry->next = NULL;
  124.     for (i = 0  ;  i < LANG_COUNT  ;  ++i)
  125.     entry->value[i] = 0;
  126.  
  127.     entry->value[(int)language] = value;
  128.  
  129.     return entry;
  130. }
  131.  
  132. /*  Note that it is assumed that a "value" of zero means an undefined keyword
  133.  *  and clients of this function should observe this. Also, all keywords added
  134.  *  should be added in lower case. If we encounter a case-sensitive language
  135.  *  whose keywords are in upper case, we will need to redesign this.
  136.  */
  137. extern void addKeyword( string, language, value )
  138.     const char *const string;
  139.     langType language;
  140.     int value;
  141. {
  142.     const unsigned int hashedValue = hashValue(string);
  143.     hashEntry *tableEntry = getHashTableEntry(hashedValue);
  144.     hashEntry *entry = tableEntry;
  145.  
  146.     if (entry == NULL)
  147.     {
  148.     hashEntry **const table = getHashTable();
  149.     hashEntry *new = newEntry(string, language, value);
  150.  
  151.     table[hashedValue] = new;
  152.     }
  153.     else
  154.     {
  155.     hashEntry *prev = NULL;
  156.  
  157.     while (entry != NULL)
  158.     {
  159.         if (strcmp(string, entry->string) == 0)
  160.         {
  161.         entry->value[language] = value;
  162.         break;
  163.         }
  164.         prev = entry;
  165.         entry = entry->next;
  166.     }
  167.     if (entry == NULL)
  168.     {
  169.         hashEntry *new = newEntry(string, language, value);
  170.  
  171.         Assert(prev != NULL);
  172.         prev->next = new;
  173.     }
  174.     }
  175. }
  176.  
  177. extern int lookupKeyword( string, language )
  178.     const char *const string;
  179.     langType language;
  180. {
  181.     const unsigned int hashedValue = hashValue(string);
  182.     hashEntry *entry = getHashTableEntry(hashedValue);
  183.     int value = 0;
  184.  
  185.     Assert(language < LANG_COUNT);
  186.  
  187.     while (entry != NULL)
  188.     {
  189.     if (strcmp(string, entry->string) == 0)
  190.     {
  191.         value = entry->value[language];
  192.         break;
  193.     }
  194.     entry = entry->next;
  195.     }
  196.     return value;
  197. }
  198.  
  199. #ifdef DEBUG
  200.  
  201. static void printEntry __ARGS((const hashEntry *const entry));
  202. static void printEntry( entry )
  203.     const hashEntry *const entry;
  204. {
  205.     unsigned int i;
  206.  
  207.     printf("  %-15s", entry->string);
  208.  
  209.     for (i = 0  ;  i < LANG_COUNT  ;  ++i)
  210.     printf("%-7s  ",
  211.            entry->value[i] == 0 ? "" : getLanguageName((langType)i));
  212.     printf("\n");
  213. }
  214.  
  215. static unsigned int printBucket __ARGS((const unsigned int i));
  216. static unsigned int printBucket( i )
  217.     const unsigned int i;
  218. {
  219.     hashEntry **const table = getHashTable();
  220.     hashEntry *entry = table[i];
  221.     unsigned int measure = 1;
  222.     boolean first = TRUE;
  223.  
  224.     printf("%2d:", i);
  225.     if (entry == NULL)
  226.     printf("\n");
  227.     else while (entry != NULL)
  228.     {
  229.     if (! first)
  230.         printf("    ");
  231.     else
  232.     {
  233.         printf(" ");
  234.         first = FALSE;
  235.     }
  236.     printEntry(entry);
  237.     entry = entry->next;
  238.     measure = 2 * measure;
  239.     }
  240.     return measure - 1;
  241. }
  242.  
  243. extern void printKeywordTable()
  244. {
  245.     unsigned long emptyBucketCount = 0;
  246.     unsigned long measure = 0;
  247.     unsigned int i;
  248.  
  249.     for (i = 0  ;  i < TableSize  ;  ++i)
  250.     {
  251.     const unsigned int pass = printBucket(i);
  252.  
  253.     measure += pass;
  254.     if (pass == 0)
  255.         ++emptyBucketCount;
  256.     }
  257.  
  258.     printf("spread measure = %ld\n", measure);
  259.     printf("%ld empty buckets\n", emptyBucketCount);
  260. }
  261.  
  262. #endif
  263.